package com.demo.java.OD351_400.OD390;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【电脑病毒感染(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146243225
 */
public class OdMain {
    // 使用快速扫描器类来优化输入
    static class FastScanner {
        BufferedReader bufferedReader;
        StringTokenizer tokenizer;

        public FastScanner() {
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }

        // 读取下一个输入的字符串
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreElements()) {
                try {
                    tokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        // 读取下一个整数
        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        int numNodes = scanner.nextInt();  // 网络节点数 N
        int numEdges = scanner.nextInt();  // 网络连接数 M

        // 创建图的邻接表
        List<int[]>[] graph = new List[numNodes + 1];  // 使用数组表示图，节点编号从1开始
        for (int i = 1; i <= numNodes; ++i) {
            graph[i] = new ArrayList<>();
        }

        // 输入网络连接的信息
        for (int i = 0; i < numEdges; ++i) {
            int nodeA = scanner.nextInt();  // 第一个节点
            int nodeB = scanner.nextInt();  // 第二个节点
            int travelTime = scanner.nextInt();  // 传播时间
            graph[nodeA].add(new int[]{nodeB, travelTime});  // 在节点A中添加节点B的信息
        }

        int startNode = scanner.nextInt();  // 起始节点，即病毒的源节点
        // 使用优先队列来存储待访问的节点
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[0]));
        Set<Integer> visitedNodes = new HashSet<>();  // 用来记录访问过的节点

        // 将源节点加入优先队列，初始时间为0
        minHeap.add(new int[]{0, startNode});

        // Dijkstra算法的核心处理过程
        while (!minHeap.isEmpty()) {
            int[] currentArr = minHeap.poll();  // 取出当前时间最短的节点
            int currentTime = currentArr[0];
            int currentNodeId = currentArr[1];
            visitedNodes.add(currentNodeId);  // 标记当前节点为已访问

            // 如果所有节点都已访问，则输出当前时间
            if (numNodes == visitedNodes.size()) {
                System.out.println(currentTime);
                return;
            }

            // 扩展当前节点的邻居节点
            for (int[] neighbor : graph[currentNodeId]) {
                int nextNodeId = neighbor[0];  // 邻居节点ID
                int costTime = neighbor[1];    // 邻居节点传播时间
                if (!visitedNodes.contains(nextNodeId)) {
                    minHeap.add(new int[]{currentTime + costTime, nextNodeId});  // 将邻居节点加入优先队列
                }
            }
        }

        // 如果还有未访问的节点，则说明无法传播到所有节点，输出-1
        if (numNodes != visitedNodes.size()) {
            System.out.println(-1);
        }
    }
}